package com.mango.leet.code.easy;

/**
 * 283. 移动零
 */

import java.util.Arrays;

/**
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 *
 * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: nums = [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * 示例 2:
 *
 * 输入: nums = [0]
 * 输出: [0]
 *  
 *
 * 提示:
 *
 * 1 <= nums.length <= 104
 * -231 <= nums[i] <= 231 - 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/move-zeroes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LC283_MoveZeroes {

    public static void main(String[] args) {
        int[] nums = {0,1,0,3,0,1,3,4,0,12};
        new Solution().moveZeroes2(nums);
        System.out.println(Arrays.toString(nums));
    }

    static class Solution {
        // 双指针
        public void moveZeroes2(int[] nums) {
            int l = 0, r = 0;
            int n = nums.length;
            while(r < n){
                // 右边的数不等0
                if(nums[r] != 0){
                    // 将r的值赋给l
                    nums[l] = nums[r];
                    l++;
                }
                r++;
            }
            // 将l后面的值补0
            while(l < n){
                nums[l] = 0;
                l++;
            }
        }

        public void moveZeroes(int[] nums) {
            int len = nums.length;
            int move = 0;
            for(int i=0;i<len-move;i++){
                for(int j=0;j<len-1;j++){
                    // 0 冒泡
                    if(nums[j] == 0 && nums[j+1] != 0){
                        swap(nums,j,j+1);
                        move++;
                    }
                }
            }

        }
        // 交换数组下标
        public void swap(int[] nums,int i,int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}
